// 1-17 实例-17 求两数的最大公约数
/**
 * 最大公约数，GCD 最小公倍数：LCM
 * great 全部；大的；重大的；强烈的；极大的；久的；大写的
 * greatest common divisor 最大公约数
 * least common multiple 最小公倍数
 * 
 * 用户输入两个数，求这两个数的最大公约数。
 * 
 * 最大公约数计算gcd：两数能同时被 i 整除。
 * 最小公倍数计算：两数相乘 / 最大公约数。
 */
#include <iostream>
int gcd1(int a, int b);
int gcd2(int a, int b);
int gcd3(int a, int b);
int main(void)
{
  int a, b;
  std::cout << "请输入两个数:";
  std::cin >> a >> b;
  // std::cout << "GCD:" << gcd1(a, b) << std::endl;
  // std::cout << "GCD:" << gcd2(a, b) << std::endl;
  std::cout << "GCD:" << gcd3(a, b) << std::endl;
  printf("---------------end-----------------\n");
  return 0;
}

int gcd1(int a, int b)
{
  while (a != b)
  {
    if (a > b)
    {
      a -= b;
    }
    else
    {
      b -= a;
    }
  }
  return a;
};

int gcd2(int a, int b)
{
  // 如果b>a交换这两个数
  int res;
  if (b > a)
  {
    int t = a;
    a = b;
    b = t;
  }
  for (int i = 1; i < b; i++)
  {
    if (a % i == 0 && b % i == 0)
    {
      res = i;
    }
  }
  return res;
}

// 求 gcd 我们可以使用辗转相除法，即 gcd(a,b)=gcd(b,a%b)。
// 递归计算最小公倍数
int gcd3(int x, int y)
{
  return y ? gcd3(y, x % y) : x;
}